/*
 * @lc app=leetcode.cn id=854 lang=typescript
 *
 * [854] 相似度为 K 的字符串
 */

// @lc code=start
type Data = [string, number];

function swap(cur: string, pos: number, j: number): string {
  const tmp: string[] = [...cur];
  [tmp[pos], tmp[j]] = [tmp[j], tmp[pos]];
  return tmp.join('');
}

function kSimilarity(s1: string, s2: string): number {
  const n = s1.length;
  const visited = new Set<string>();
  const queue: Data[] = [];
  // 初始化
  queue.push([s1, 0]);
  visited.add(s1);
  let step = 0;
  // 广搜
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      let [cur, pos] = queue.shift()!;
      if (cur === s2) return step;
      // 找到 s1 第一个需要交换的位置
      while (pos < n && cur[pos] === s2[pos]) {
        pos++;
      }
      // 遍历需要交换的字符
      for (let j = pos + 1; j < n; j++) {
        if (cur[j] === s2[j]) continue;
        if (cur[j] === s2[pos]) {
          const next = swap(cur, pos, j);
          if (!visited.has(next)) {
            queue.push([next, pos + 1]);
            visited.add(next);
          }
        }
      }
    }
    step++;
  }

  return step;
}
// @lc code=end
